
/*
 *  BloomFilterMap.cpp
 *
 *	code reference to https://github.com/karthikmit/NikBloomFilter
 *
 *	Crane made some expand: 
 *
 *		1. bit array can be loaded from string
 *		2. bit array can be saved to File
 *		3. bit array can search with string, not only byte array
 *		4. fix memory free issue
 *************************************************************************
 *
 *  Description:
 *      This file implements the bloom filter with some independ MD5 hash 
 *		funcitons, including create, insert and query operations.
 *
 */

#include <math.h>
#include <algorithm>
#include <iterator>
#include "MD5.h"
#include "BloomFilter.h"

BloomFilter::BloomFilter(unsigned int expectedFields, double falseProbability)
{
	const double ln2 = 0.693147;
//	const double falseDropBase = 0.6185;
	const double d = 1.442695;

	double bufferingFactor = log10(1.0 / falseProbability) / log10(2.0);

	//Bloom filter has zero fields inserted, all bits have been set is zero
	//to calculate m 
	unsigned int BloomSize = (unsigned int)( d * bufferingFactor * expectedFields );
	bloomBits.resize(BloomSize, 0);

	//to caulcate how many hash function to used
	NumberOfIndices = (unsigned int)(ln2 * BloomSize / expectedFields);

}

bool BloomFilter::Insert(vector<unsigned char>& inBytes)
{
	unsigned int *indicesToSet = GetIndices(inBytes);

	for(unsigned int i = 0; i < NumberOfIndices; ++i)
	{
		bloomBits[indicesToSet[i]] = 1;
	}

	inBytes.clear();
	delete []indicesToSet;
	
	return true;
}

bool BloomFilter::Insert(const string& inputLine)
{
	int length = inputLine.size();
	if ((length > 0) && (inputLine[length - 1] == '\n'))
	{
		--length;
	}

	if ((length > 0) && (inputLine[length - 1] == '\r'))
	{
		--length;
	}

	vector<unsigned char> bytesArr(length);

	const char *input = inputLine.c_str();
	copy(input, input+length, bytesArr.begin());

	return Insert(bytesArr);
}

// Convert into a vector and call Insert(vector);
bool BloomFilter::Insert(unsigned char *inBytes, int length)
{
	vector<unsigned char> inBytesVector(length);
	copy(inBytes, inBytes + length, inBytesVector.begin());
	return Insert(inBytesVector);
}


// Return 16 Bytes of MD5ied input of size, inputSize.
unsigned char* BloomFilter::MD5Bytes(unsigned char* input, unsigned int inputSize)
{
	MD5 context; // MD5 Module: RSA Data Security, Inc., MD5 message-digest algorithm

	context.update(input, inputSize); 
	context.finalize();
	
	return context.raw_digest();
}

unsigned int * BloomFilter::GetMD5Indices(unsigned char* input, int size)
{
	unsigned char* hashBytes = MD5Bytes(input, size);
	return (unsigned int *) hashBytes;
}

// Get 'numberOfIndices' of integers of MD5 output for inBytes.
unsigned int * BloomFilter::GetBloomIndices(vector<unsigned char>& inBytes, int numberOfIndices = 4)
{
	const int sizeOfInteger = sizeof(int);

	int toBeSpawnedoutBytesArray = 1;
	if( numberOfIndices > sizeOfInteger)  //because 32bit integer is 4 bytes
	{
		toBeSpawnedoutBytesArray = numberOfIndices / 4;
		if( numberOfIndices % sizeOfInteger != 0)
		{
			++toBeSpawnedoutBytesArray;
		}
	}

	unsigned int inputSize = inBytes.size();
	unsigned char *input = new unsigned char[inputSize];
	unsigned int *returnValue = new unsigned int[numberOfIndices];

	copy(inBytes.begin(), inBytes.end(), input);

	if( toBeSpawnedoutBytesArray > 1)
	{
		inputSize += 1; 
		if (input != NULL)
		{
			delete [] input; 
			input = NULL;
		}
		input = new unsigned char[inputSize];

		copy(inBytes.begin(), inBytes.end(), input);
		unsigned char pad = 0;
		vector<unsigned int> indicesVector;
		
		while(toBeSpawnedoutBytesArray--)
		{
			input[inputSize-1] = pad++;
			unsigned int *out = GetMD5Indices(input, inputSize);

			for( int k = 0; k < sizeOfInteger; ++k)
			{
				indicesVector.push_back(out[k]);
			}
			delete []out;
		}
		
		copy(indicesVector.begin(), indicesVector.begin() + numberOfIndices, returnValue);
	}
	else
	{
		returnValue = GetMD5Indices(input, inputSize);
	}
	if (input != NULL)
	{
		delete [] input; 
	}
	return returnValue;
}

unsigned int *BloomFilter::GetIndices(vector<unsigned char>& inBytes)
{
	unsigned int *indicesToSet = GetBloomIndices(inBytes, NumberOfIndices);
	for(unsigned int i = 0, bloomSize = bloomBits.size(); i < NumberOfIndices; ++i)
	{
		indicesToSet[i] = indicesToSet[i] % bloomSize;
	}

	inBytes.clear();

	return indicesToSet;
}

//to search key in bit array
bool BloomFilter::IsPresent(vector<unsigned char>& inBytes)
{
	unsigned int *indicesToSet = GetIndices(inBytes);

	bool result = true;
	for(unsigned int i = 0; i < NumberOfIndices; ++i)
	{
		if(!bloomBits[indicesToSet[i]])
		{
			result = false;
			break;
		}
	}

	delete []indicesToSet;
	
	return result;
}

bool BloomFilter::IsPresent(const string& key)
{
	int length = key.size();

	if ((length > 0) && (key[length - 1] == '\n'))
	{
		--length;
	}

	if ((length > 0) && (key[length - 1] == '\r'))
	{
		--length;
	}

	vector<unsigned char> bytesArr(length);

	const char *input = key.c_str();
	copy(input, input+length, bytesArr.begin());

	return IsPresent(bytesArr);
}

bool BloomFilter::IsPresent(unsigned char* inBytes, int length)
{
	vector<unsigned char> inBytesVector(length);
	copy(inBytes, inBytes + length, inBytesVector.begin());
	return IsPresent(inBytesVector);
}

//load from string, string format: 010111000
//each char to represtent a bit
void BloomFilter::LoadFromString(const string& inputLine)
{
	const char *p = inputLine.c_str();
	for(unsigned i=0, len = inputLine.length(); i<len; ++i)
	{
		bloomBits[i] = ( p[i] == '1' );
	}
}

//only for debug information
string BloomFilter::ToString(void)
{
	string s;
	for(unsigned int i = 0, len = bloomBits.size(); i < len; ++i)
	{
		s.append( bloomBits[i] ? "1" : "0");
	}
	return s;
}

//Write the structre(bit array to file)
void BloomFilter::WriteToFile(ofstream& outputFile)
{
	for(unsigned int i = 0, len = bloomBits.size(); i < len; ++i)
	{
		outputFile.write(bloomBits[i] ? "1" : "0", 1);
	}
}

